package com.shm.leetcode;

/**
 * 剑指 Offer 11. 旋转数组的最小数字
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
 *
 * 示例 1：
 *
 * 输入：[3,4,5,1,2]
 * 输出：1
 * 示例 2：
 *
 * 输入：[2,2,2,0,1]
 * 输出：0
 * @author SHM
 */
public class MinArray {
    public int minArray(int[] numbers) {
        int min = Integer.MAX_VALUE;
        for(int i:numbers){
            if(i<min){
                min = i;
            }
        }
        return min;
    }

    /**
     * 解题思路：
     * 为精简篇幅，本文将数组 numbersnumbers 缩写为 numsnums 。
     *
     * 如下图所示，寻找旋转数组的最小元素即为寻找 右排序数组 的首个元素 nums[x]nums[x] ，称 xx 为 旋转点 。
     *
     *
     *
     * 排序数组的查找问题首先考虑使用 二分法 解决，其可将 遍历法 的 线性级别 时间复杂度降低至 对数级别 。
     *
     * 算法流程：
     * 初始化： 声明 ii, jj 双指针分别指向 numsnums 数组左右两端；
     * 循环二分： 设 m = (i + j) / 2m=(i+j)/2 为每次二分的中点（ "/" 代表向下取整除法，因此恒有 i \leq m < ji≤m<j ），可分为以下三种情况：
     * 当 nums[m] > nums[j]nums[m]>nums[j] 时： mm 一定在 左排序数组 中，即旋转点 xx 一定在 [m + 1, j][m+1,j] 闭区间内，因此执行 i = m + 1i=m+1；
     * 当 nums[m] < nums[j]nums[m]<nums[j] 时： mm 一定在 右排序数组 中，即旋转点 xx 一定在[i, m][i,m] 闭区间内，因此执行 j = mj=m；
     * 当 nums[m] = nums[j]nums[m]=nums[j] 时： 无法判断 mm 在哪个排序数组中，即无法判断旋转点 xx 在 [i, m][i,m] 还是 [m + 1, j][m+1,j] 区间中。解决方案： 执行 j = j - 1j=j−1 缩小判断范围，分析见下文。
     * 返回值： 当 i = ji=j 时跳出二分循环，并返回 旋转点的值 nums[i]nums[i] 即可。
     * 正确性证明：
     * 当 nums[m] = nums[j]nums[m]=nums[j] 时，无法判定 mm 在左（右）排序数组，自然也无法通过二分法安全地缩小区间，因为其会导致旋转点 xx 不在区间 [i, j][i,j] 内。举例如下：
     *
     * 设以下两个旋转点值为 00 的示例数组，则当 i = 0i=0, j = 4j=4 时 m = 2m=2 ，两示例结果不同。
     * 示例一 [1, 0, 1, 1, 1][1,0,1,1,1] ：旋转点 x = 1x=1 ，因此 m = 2m=2 在 右排序数组 中。
     * 示例二 [1, 1, 1, 0, 1][1,1,1,0,1] ：旋转点 x = 3x=3 ，因此 m = 2m=2 在 左排序数组 中。
     *
     * 而证明 j = j - 1j=j−1 正确（缩小区间安全性），需分为两种情况：
     *
     * 当 x < jx<j 时： 易得执行 j = j - 1j=j−1 后，旋转点 xx 仍在区间 [i, j][i,j] 内。
     *
     * 当 x = jx=j 时： 执行 j = j - 1j=j−1 后越过（丢失）了旋转点 xx ，但最终返回的元素值 nums[i]nums[i] 仍等于旋转点值 nums[x]nums[x] 。
     *
     * 由于 x = jx=j ，因此 nums[x] = nums[j] = nums[m] \leq number[i]nums[x]=nums[j]=nums[m]≤number[i] ;
     * 又由于 i \leq m <ji≤m<j 恒成立，因此有 m < xm<x ，即此时 mm 一定在左排序数组中，因此 nums[m] \geq nums[i]nums[m]≥nums[i] ;
     * 综合 1. , 2. ，可推出 nums[i] = nums[m]nums[i]=nums[m] ，且区间 [i, m][i,m] 内所有元素值相等，即有：
     * nums[i] = nums[i+1] = \cdots = nums[m] = nums[x]
     * nums[i]=nums[i+1]=⋯=nums[m]=nums[x]
     *
     * 此时，执行 j = j - 1j=j−1 后虽然丢失了旋转点 xx ，但之后区间 [i, j][i,j] 只包含左排序数组，二分下去返回的一定是本轮的 nums[i]nums[i] ，而其与 nums[x]nums[x] 相等。
     * 综上所述，此方法可以保证返回值 nums[i]nums[i] 等于旋转点值 nums[x]nums[x] ，但在少数特例下 i \ne xi
     * 
     * ​
     *  =x ；而本题目只要求返回 “旋转点的值” ，因此本方法正确。
     *
     * 补充思考： 为什么本题二分法不用 nums[m]nums[m] 和 nums[i]nums[i] 作比较？
     *
     * 二分目的是判断 mm 在哪个排序数组中，从而缩小区间。而在 nums[m] > nums[i]nums[m]>nums[i]情况下，无法判断 mm 在哪个排序数组中。本质上是由于 jj 初始值肯定在右排序数组中； ii 初始值无法确定在哪个排序数组中。举例如下：
     *
     * 对于以下两示例，当 i = 0, j = 4, m = 2i=0,j=4,m=2 时，有 nums[m] > nums[i] ，而结果不同。
     * [1, 2, 3, 4 ,5][1,2,3,4,5] 旋转点 x = 0x=0 ： mm 在右排序数组（此示例只有右排序数组）；
     * [3, 4, 5, 1 ,2][3,4,5,1,2] 旋转点 x = 3x=3 ： mm 在左排序数组。
     *
     * 复杂度分析：
     * 时间复杂度 O(\log_2 N)O(log
     * 2
     * ​
     *  N) ： 在特例情况下（例如 [1, 1, 1, 1][1,1,1,1]），会退化到 O(N)O(N)。
     * 空间复杂度 O(1)O(1) ： ii , jj , mm 变量使用常数大小的额外空间。
     *
     * 作者：Krahets
     * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5055b1/
     * @param numbers
     * @return
     */
    public int minArray_2(int[] numbers) {
        int i=0,j=numbers.length-1;
        while (i<j){
            int m = (j-i)/2+i;
            if(numbers[m]>numbers[j]){
                i=m+1;
            }else if(numbers[m]<numbers[j]){
                j=m;
            }else {
                j--;
            }
        }
        return numbers[i];
    }

    /**
     * 实际上，当出现 nums[m] = nums[j]nums[m]=nums[j] 时，一定有区间 [i, m][i,m] 内所有元素相等 或 区间 [m, j][m,j] 内所有元素相等（或两者皆满足）。对于寻找此类数组的最小值问题，可直接放弃二分查找，而使用线性查找替代。
     *
     * 作者：Krahets
     * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5055b1/
     * @param numbers
     * @return
     */
    public int minArray_3(int[] numbers) {
        int i=0,j=numbers.length-1;
        while (i<j){
            int m = (j-i)/2+i;
            if(numbers[m]>numbers[j]){
                i=m+1;
            }else if(numbers[m]<numbers[j]){
                j=m;
            }else {
                int x = i;
                for (int k = i+1; k < j; k++) {
                    if(numbers[k]<numbers[x]){
                        x= k;
                    }
                }
                return numbers[x];
            }
        }
        return numbers[i];
    }
}
